package day008;

public class KnapsackProblem2 {
    public static void main(String[] args) {

        //n=3 当前背包能装多少个物品
        //w=4 当前背包能装多少重量
        int[] wt = {2, 1, 3, 1, 1};
        System.out.println(wt.length);
        int[] val = {4, 2, 3, 5, 7};
        System.out.println(knapsack(wt.length, 4, wt, val));
    }


    /**
     * @param itemNums
     * @param capacity
     * @param wt
     * @param val
     * @return
     */
    static int knapsack(int itemNums, int capacity, int[] wt, int[] val) {
        KnapData[][] dp = new KnapData[itemNums + 1][capacity + 1];
        for (int i = 0; i <= itemNums; i++) {
            for (int j = 0; j <= capacity; j++) {
                KnapData knapData = new KnapData();
                knapData.value = 0;
                knapData.weight = 0;
                dp[i][j] = knapData;
            }
        }
        for (int currentNums = 1; currentNums <= itemNums; currentNums++) {
            for (int currentCapacity = 1; currentCapacity <= capacity; currentCapacity++) {
                if ((currentCapacity - wt[currentNums - 1]) >= 0) {
                    if ((currentCapacity - dp[currentNums - 1][currentCapacity - wt[currentNums - 1]].weight - wt[currentNums - 1]) < 0) {
                        dp[currentNums][currentCapacity].value = dp[currentNums - 1][currentCapacity].value;
                        dp[currentNums][currentCapacity].weight = dp[currentNums - 1][currentCapacity].weight;
                    } else {
                        if (dp[currentNums - 1][currentCapacity - wt[currentNums - 1]].value + val[currentNums - 1] > dp[currentNums - 1][currentCapacity].value) {
                            dp[currentNums][currentCapacity].value = dp[currentNums - 1][currentCapacity - wt[currentNums - 1]].value + val[currentNums - 1];
                            dp[currentNums][currentCapacity].weight = dp[currentNums - 1][currentCapacity - wt[currentNums - 1]].weight + wt[currentNums - 1];
                        } else {
                            dp[currentNums][currentCapacity].value = dp[currentNums - 1][currentCapacity].value;
                            dp[currentNums][currentCapacity].weight = dp[currentNums - 1][currentCapacity].weight;
                        }
                    }
                } else {
                    dp[currentNums][currentCapacity].value = dp[currentNums - 1][currentCapacity].value;
                    dp[currentNums][currentCapacity].weight = dp[currentNums - 1][currentCapacity].weight;
                }

            }
        }
        for (int i = 0; i <= itemNums; i++) {
            for (int j = 0; j <= capacity; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println();
        }
        return dp[itemNums][capacity].value;
    }
}
